/**
 * 
 */
package leetCode;

import java.util.HashSet;

/**
 * @author zhongfang
 *
 */
public class EqualTreePartition {
	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}
	
    public boolean checkEqualTree(TreeNode root) {
        HashSet<Integer> treeSum=new HashSet<>();
        int total=getSum(treeSum,root);
        if(root==null||(root.left==null&&root.right==null)){
        	return false;
        }
        if(total%2==0&&treeSum.contains(total/2)){
        	return true;
        }
        return false;
    }
	private int getSum(HashSet<Integer> treeSum, TreeNode root) {
		if(root==null){
			return 0;
		}
		int left=getSum(treeSum, root.left);
		int right=getSum(treeSum, root.right);
		int curSum=left+right+root.val;
		treeSum.add(curSum);
		return curSum;
	}
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
